#include "doubleL.h"

#define FALSE 0
#define TRUE 1
#define OK 2
#define ERROR -1
#define OVERFLOW -2

#define ERROR_MSG_OVERFLOW "Fail to allocate memory!"
#define ERROR_MSG_POSITION "Illegal position!"
#define ERROR_MSG_NOTEXIST "Element not exist!"

list* list_init()
{ 
	list* L;
  	L=(list*)malloc(sizeof(list_node));
  	if(L!=NULL)
  	{
  		L->next=L->prev=L;
  		return L;
  	}
  	else
  	{
  		/*fprintf(stderr,"fail to  malloc memeory !\n");*/
  		return NULL;	
  	}
    
}

void list_destroy(list *L)
{ 
	list *q,*p=L->next; 
  	while(p!=L) 
  	{
    	q=p->next;
    	free(p);
    	p=q;
  	}
  	free(L);
  	L=NULL;
}

int list_empty (list *L)
{ 
  	if(L->next==L&&L->prev==L)
    	return TRUE;
  	else
    	return FALSE;
}

int list_length(list *L)
{ 
  	int count=0;
  	list *p=L->next; 
  	while(p!=L) 
  	{
    	count++;
    	p=p->next;
  	}
  	return count;
}

list* list_get_pointer(list *L,int pos)
{
	int i;
  	list *p=L; 
  	if(pos<0||pos>list_length(L)) 
  	{
    	/*fprintf(stderr,"illeagal position !\n");*/
    	return NULL;
    }
  	for(i=1;i<=pos;i++)
  	{
    	p=p->next;
    }
  	return p;
}

ElemType list_get_element(list *L,int pos)
{ 
  	int i=1; 
  	list *p=L->next;
  	if(pos<0||pos>list_length(L)) 
  	{
  		return NULL;	
  	}

  	while( p != L && i != pos )
  	{
  		p = p->next;
  		i ++;
  	}
  	if(p==L||i>pos)
  	{
    	return NULL;
    }
    else
    {
    	return p->data;
    }
}

int list_get_index( list *L, list_node* pnode )
{
    int index = 0;
	list * p = L;
	if(L == NULL )
	{
		return ERROR;
	}

	while( p != pnode )
	{
		p = p->next;
		index ++;		
	}
	if( p == L )
	{
		return ERROR;
	}
	return index;
}

/*insert a node after the node in pos-1*/
int list_insert(list *L,int pos,ElemType e)
{ 
  	list *p,*tnode;
  	if(pos<1||pos>list_length(L)+1) 
  	{
  		return ERROR;
  	}
    
  	p=list_get_pointer(L,pos-1); 
  	if(!p) 
  	{
  		return ERROR;
  	}	
  	tnode=(list*)malloc(sizeof(list_node));
  	if(!tnode)
  	{
  		return OVERFLOW;
  	}
  	tnode->data=e;
  	tnode->prev=p; 
  	tnode->next=p->next;
  	p->next->prev=tnode;
  	p->next=tnode;
  	return OK;
}

int list_append(list *L,ElemType e)
{ 
  	list *p,*tnode;
  	p=L->prev;	
  	tnode=(list*)malloc(sizeof(list_node));
  	if(!tnode)
  	{
  		return OVERFLOW;
  	}

  	tnode->data=e;
  	p->next=tnode;
  	tnode->prev=p; 
  	tnode->next=L;
  	L->prev=tnode;
  	return OK;
}

int list_remove(list *L,int pos)
{ 
  	list *p;
  	if(pos<1||pos>list_length(L)+1) 
  	{
  		return ERROR;
  	}
  	p=list_get_pointer(L,pos);
  	p->prev->next=p->next;
  	p->next->prev=p->prev;
  	free(p);
  	return OK;
}

void list_swap_nodes( list_node* low, list_node* high )
{

	list_node* tmp = NULL;
	if( low->next == high )
	{			

		low->prev->next = high;
		high->prev = low->prev;			
		low->prev = high;			
		low->next = high->next;			
			
		high->next->prev = low;
		high->next = low;

		tmp = high;
		high = low;
		low = tmp;						
	}
	else
	{							
		low->prev->next = high;
		low->next->prev = high;
			
		high->prev->next = low;
		high->next->prev = low;		

		tmp = low->prev;
		low->prev = high->prev;
		high->prev = tmp;
		
		tmp = low->next;
		low->next = high->next;
		high->next = tmp;
			
		tmp = high;
		high = low;
		low = tmp;			
	}	
}


void list_swap_nodes_simple( list_node* low, list_node* high )
{
	ElemType t;
	t=low->data;
	low->data=high->data;
	high->data=t;
}

int list_sort_key(list_node* pnode)
{
	return ((PCB*)pnode->data)->cpu_time- ((PCB*)pnode->data)->completed_cpu_time;
}

void list_sort_simple( list *L)
{
	list* q;
	list* p=L->next;

	while( p != L)
  	{
  		q=p->next;
  		while(q!=L)
  		{
  			if(list_sort_key(p)>list_sort_key(q))
  			{
  				list_swap_nodes_simple(p,q);
  			}
  			q=q->next;
  		}
		p = p->next;
  	}
}

void list_print(list* L)
{
	list *p=L->next;
  	while(p!=L)
  	{
    	printf("(%d,%d,%d)", ((PCB*)p->data)->pid,((PCB*)p->data)->priority,((PCB*)p->data)->time_slice);
    	p=p->next;
  	}
  	printf("\n");
}
